In colour printing environments the total uncompressed size of a generated pixel image is often large and it is advantageous to avoid storing the entire image uncompressed. Such pixel images are typically generated in raster or band order. In particular, pixels, scanlines, groups of scanlines (bands), or tiles, each defining a particular minimal coding unit, are emitted in a stream from a raster image processor that has as input an object graphic description of the page to be printed. The stream data is often formed by pixel colour values, but may be other information relating to the image being generated. Collectively these types of information shall be referred to herein as image data.
Hybrid compression techniques may be applied to image data in order to improve compression. Within a hybrid system there are at least two compression engines (encoders) used alongside one another.
Hybrid compression necessitates some form of image segmentation or differentiation to thereby identify what image data is to be compressed with one type of compressor, and what image data is to be compressed with another type of compressor. Examples of image segmentation exist throughout the art and include region growing and edge detection, to name but two.
Image data can be compressed losslessly using any general lossless compression method. Run-length encoding, entropy encoding, dictionary-based methods, and various combinations of those have been used in lossless image compression. With an appropriately segmented image, taking advantage of any image data information about neighbouring (or adjacent) pixel positions within a segment or region tends to improve the lossless compression result for a current pixel position due to a spatial correlation between neighbouring image data values. Context set (or context) in the literature refers to the set of pixels within which the current pixel occurs and is used to encode the current pixel value. Most often the context is made of several of the pixels adjacent the position of the current pixel. U.S. Pat. No. 5,680,129 (Weinberger et. al.), published Oct. 21, 1997, describes a method in which the context comprises three immediate neighbours above the current pixel position, and the neighbour immediately to the left of the current pixel position. The method determines a predicted value for the current pixel and encodes the residual of (difference between) the actual pixel value and the predicted value.
The paper “Lossless Image Compression with Lossy Image Using Adaptive Prediction and Arithmetic Coding”; Seishi Takamura, Mikio Takagi: Data Compression Conference 1994, pp. 166-174, 1994, proposes a method which uses up to ten pixels, some of which are immediate neighbours and the rest are adjacent to those immediate neighbours. The context set is computed amongst those ten pixels. United States Patent Publication No. 20060050972 A1 (Reznic) published Mar. 9, 2006 uses a method where the context set is constructed amongst pixels lying on a straight line between two chosen neighbouring pixels. United States Patent Publication No. 20070154106 A1 (Koziarz) published Jul. 5, 2007 describes a context set comprising pixels at predetermined offsets from the current pixel. These offsets are adaptively determined for each scanline using statistical information about the values of those pixels.
U.S. Pat. No. 6,285,790 (Schwartz), published Sep. 4, 2001, includes pixel position information to further improve compression when the image data is a collection of smaller images, such as sprites, characters, or a graphical menu. Some neighbouring pixels might be independent of the pixel being coded and, therefore are excluded from the context set of a given pixel. This method, however, does not use correlation between data from similar non-adjacent regions.
The above approaches use either a fixed context set or vary the context set according to the data profile. While a disadvantage of a fixed context set is its lack of flexibility and thus potentially smaller compression gains, dynamic context set formation is both complex and time consuming. Therefore, it is desirable to somehow combine the simplicity of a fixed context set and the flexibility of dynamic set formation.
Most context encoders in the art, including the above-mentioned, are based on a predictor known in the art as MED (Median Edge Detector), described for example in the aforementioned U.S. Pat. No. 5,680,129. The MED predictor uses the data trend over the context set in order to predict the current value. Since it is invoked at each pixel, use of the MED predictor is computationally intensive. After calculation of the residuals using MED, these can be coded using a given compression method such as Huffman coding or using Golomb codes.